package q924_minMalwareSpread;

import CommonClass.UF;

import java.util.Arrays;

public class Solution_1 {
    /*
    并查集题型：
    首先根据graph[i][j] == 1将不同的节点进行union
    此时UF结构中已经记录了每个节点其代表的size 为一个数组
    然后遍历initial中所有病毒节点 根据该节点的代表 来对不同簇中病毒节点有多少个进行计算
    需要注意的是 如果一个簇中有两个病毒节点 删掉一个是没有意义的 因为这个簇还是会被整个感染
    所以必须要找簇中只有一个病毒节点的情况
     */
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        UF uf = new UF(n);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j] == 1) uf.union(i, j);
            }
        }
        int[] count = new int[n];
        // 这里就是计算不同簇中分别有多少个病毒节点
        // 而簇是依照node的代表进行分类的 所以要用uf.find(node)
        // 例如 1 2 3 4 5的代表是1 而6 7 8 9 10的代表是7 所以如果病毒节点是2 3 8
        // 那么最后是 count[1] = 2 count[7] = 1
        for (int node : initial) {
            count[uf.find(node)]++;
        }
        int ans = -1, ansSize = -1;
        for (int node : initial) {
            // 这里包含了多个条件
            // 1 簇中必须只有一个病毒节点 否则删了没有意义
            // 2 遇到簇比当前ansSize更大的 再更新
            // 3 否则遇到一样大的 就看node的索引大小 如果小就更新
            if (count[uf.find(node)] == 1 && (uf.size[uf.find(node)] > ansSize || uf.size[uf.find(node)] == ansSize && node < ans)) {
                ans = node;
                ansSize = uf.size[uf.find(node)];
            }
        }
        // 最后发现簇里面都至少有两个病毒 就直接返回一个initial里面的最小值
        if (ans == -1) return Arrays.stream(initial).min().getAsInt();
        return ans;
    }
}
